package com.shm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: shm
 * @dateTime: 2020/11/30 9:42
 * @description: 767. 重构字符串
 * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 *
 * 若可行，输出任意可行的结果。若不可行，返回空字符串。
 *
 * 示例 1:
 *
 * 输入: S = "aab"
 * 输出: "aba"
 * 示例 2:
 *
 * 输入: S = "aaab"
 * 输出: ""
 * 注意:
 *
 * S 只包含小写字母并且长度在[1, 500]区间内。
 */
public class ReorganizeString {
    /**
     * 方法二：基于计数的贪心算法
     * 首先统计每个字母的出现次数，然后根据每个字母的出现次数重构字符串。
     *
     * 当 nn 是奇数且出现最多的字母的出现次数是 (n+1)/2(n+1)/2 时，出现次数最多的字母必须全部放置在偶数下标，否则一定会出现相邻的字母相同的情况。其余情况下，每个字母放置在偶数下标或者奇数下标都是可行的。
     *
     * 维护偶数下标 \textit{evenIndex}evenIndex 和奇数下标 \textit{oddIndex}oddIndex，初始值分别为 00 和 11。遍历每个字母，根据每个字母的出现次数判断字母应该放置在偶数下标还是奇数下标。
     *
     * 首先考虑是否可以放置在奇数下标。根据上述分析可知，只要字母的出现次数不超过字符串的长度的一半（即出现次数小于或等于 n/2n/2），就可以放置在奇数下标，只有当字母的出现次数超过字符串的长度的一半时，才必须放置在偶数下标。字母的出现次数超过字符串的长度的一半只可能发生在 nn 是奇数的情况下，且最多只有一个字母的出现次数会超过字符串的长度的一半。
     *
     * 因此通过如下操作在重构的字符串中放置字母。
     *
     * 如果字母的出现次数大于 00 且小于或等于 n/2n/2，且 \textit{oddIndex}oddIndex 没有超出数组下标范围，则将字母放置在 \textit{oddIndex}oddIndex，然后将 \textit{oddIndex}oddIndex 的值加 22。
     *
     * 如果字母的出现次数大于 n/2n/2，或 \textit{oddIndex}oddIndex 超出数组下标范围，则将字母放置在 \textit{evenIndex}evenIndex，然后将 \textit{evenIndex}evenIndex 的值加 22。
     *
     * 如果一个字母出现了多次，则重复上述操作，直到该字母全部放置完毕。
     *
     * 那么上述做法是否可以确保相邻的字母都不相同？考虑以下三种情况。
     *
     * 如果 nn 是奇数且存在一个字母的出现次数为 (n+1)/2(n+1)/2，则该字母全部被放置在偶数下标，其余的 (n-1)/2(n−1)/2 个字母都被放置在奇数下标，因此相邻的字母一定不相同。
     *
     * 如果同一个字母全部被放置在奇数下标或全部被放置在偶数下标，则该字母不可能在相邻的下标出现。
     *
     * 如果同一个字母先被放置在奇数下标直到奇数下标超出数组下标范围，然后被放置在偶数下标，由于该字母的出现次数不会超过 n/2n/2，因此该字母的最小奇数下标与最大偶数下标之差不小于 33，不可能在相邻的下标出现。证明如下：
     *
     * 当 nn 是偶数时，如果该字母的出现次数为 n/2n/2，包括 pp 个奇数下标和 qq 个偶数下标，满足 p+q=n/2p+q=n/2，最小奇数下标是 n-2p+1n−2p+1，最大偶数下标是 2(q-1)2(q−1)，最小奇数下标与最大偶数下标之差为：
     * \begin{aligned} & (n-2p+1)-2(q-1) \\ = &\ n-2p+1-2q+2 \\ = &\ n-2(p+q)+3 \\ = &\ n-2 \times \frac{n}{2}+3 \\ = &\ n-n+3 \\ = &\ 3 \end{aligned}
     * =
     * =
     * =
     * =
     * =
     * ​
     *
     * (n−2p+1)−2(q−1)
     *  n−2p+1−2q+2
     *  n−2(p+q)+3
     *  n−2×
     * 2
     * n
     * ​
     *  +3
     *  n−n+3
     *  3
     * ​
     *
     *
     * 当 nn 是奇数时，如果该字母的出现次数为 (n-1)/2(n−1)/2，包括 pp 个奇数下标和 qq 个偶数下标，满足 p+q=(n-1)/2p+q=(n−1)/2，最小奇数下标是 n-2pn−2p，最大偶数下标是 2(q-1)2(q−1)，最小奇数下标与最大偶数下标之差为：
     * \begin{aligned} & (n-2p)-2(q-1) \\ = &\ n-2p-2q+2 \\ = &\ n-2(p+q)+2 \\ = &\ n-2 \times \frac{n-1}{2}+2 \\ = &\ n-(n-1)+2 \\ = &\ 3 \end{aligned}
     * =
     * =
     * =
     * =
     * =
     * ​
     *
     * (n−2p)−2(q−1)
     *  n−2p−2q+2
     *  n−2(p+q)+2
     *  n−2×
     * 2
     * n−1
     * ​
     *  +2
     *  n−(n−1)+2
     *  3
     * ​
     * 因此，在重构字符串可行的情况下，基于计数的贪心算法可以确保相邻的字母都不相同，得到正确答案。
     * 复杂度分析
     *
     * 时间复杂度：O(n+|\Sigma|)O(n+∣Σ∣)，其中 nn 是字符串的长度，\SigmaΣ 是字符集，在本题中字符集为所有小写字母，|\Sigma|=26∣Σ∣=26。
     * 遍历字符串并统计每个字母的出现次数，时间复杂度是 O(n)O(n)。
     * 重构字符串需要进行 nn 次放置字母的操作，并遍历每个字母得到出现次数，时间复杂度是 O(n+|\Sigma|)O(n+∣Σ∣)。
     * 总时间复杂度是 O(n+|\Sigma|)O(n+∣Σ∣)。
     *
     * 空间复杂度：O(|\Sigma|)O(∣Σ∣)，其中 nn 是字符串的长度，\SigmaΣ 是字符集，在本题中字符集为所有小写字母，|\Sigma|=26∣Σ∣=26。这里不计算存储最终答案字符串需要的空间（以及由于语言特性，在构造字符串时需要的额外缓存空间），空间复杂度主要取决于统计每个字母出现次数的数组和优先队列。空间复杂度主要取决于统计每个字母出现次数的数组。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/reorganize-string/solution/zhong-gou-zi-fu-chuan-by-leetcode-solution/
     * @param S
     * @return
     */
    public String reorganizeString(String S) {
        int[] chars = new int[26];
        int maxIndex = 0;
        for (char c : S.toCharArray()) {
            chars[c-'a']++;
            maxIndex = Math.max(maxIndex,chars[c-'a']);
        }
        int length = S.length();
        if (maxIndex>(length+1)/2){
            return "";
        }
        char[] ans = new char[length];
        int evenIndex = 0,oddIndex = 1;
        int halfIndex = length/2;
        for (int i = 0; i < 26; i++) {
            char c = (char)('a'+i);
            while (chars[i]>0&&chars[i]<=halfIndex&&oddIndex<length){
                chars[i]--;
                ans[oddIndex]=c;
                oddIndex+=2;
            }
            while (chars[i]>0){
                chars[i]--;
                ans[evenIndex]=c;
                evenIndex+=2;
            }
        }
        return new String(ans);
    }
}
